#include <iostream>
#include <cmath>
using namespace std;
// 记录可行方案个数
int sum=0;
// 表示皇后个数，由用户输入
int n;
// 输出当前找到的一个可行解，只在搜索到叶节点时才会调用
int output(int  x[]){
    int i;
    for(i=1;i<=n;i++){
        cout << "(" << i << "," << x[i] << ")" << " ";
    }
    cout << endl;
    return 0;
}

// 对当前行k以上的所有行（即1到k-1行）逐行进行检查
bool Place(int k,int  x[]){
    int i;
    for(i=1;i<k;i++){
        if(abs(i-k)==abs(x[i]-x[k]) || x[i]==x[k])
            return false;
    }
    return true;

}


// 见上文详解
int Backtrack(int k,int  x[]){
    int i;
    if(k>n){//如果是叶节点，直接输出找到的一个解
        output(x);
        sum++;
    }
    else{//内部节点，如果满足约束条件，继续深度搜索 。i代表列数，从1到n
        for(i=1;i<=n;i++){
            x[k]=i;
            if(Place(k,x))
                Backtrack(k+1,x);
        }
    }


}

int main(){
    int *x,i;

    cout << "输入皇后个数:" << endl;
    cin >> n;
    cout << endl;

    // 数组保存问题的解,表示皇后i放在棋盘的第i行第x[i]列
    x=new int[n+1];
    // 初始时各元素都为0
    for(i=0;i<=n;i++){
        x[i]=0;
    }

    Backtrack(1,x);

    cout << endl;
    cout << "解的个数：" << sum << endl;

    system("pause");
    return 0;
}